#include<stdio.h>

#include "07_bst_lib.h"

// 删除BST的元素

//递归法
void demo1(){
    // 创建元素
    //创建二叉树
    struct TreeNode* root=NULL;

    // 用户输入数据: 5 3 7 2 4 6 8 13 -10 /
    printf("Pls input some int, end with /\n");
    int num;
    while (scanf("%d", &num) == 1 ){
        root = insert(root, num);
    }

    // 打印树
    printTree(root, 0, "");
    inOrder(root);
    printf("\n");

    // 吃掉一个换行符
    getchar();

    //2.输入想删除的值
    printf("Which value you want to delete? > "); // 可以依次尝试 -10, 13, 8, 5, 甚至不存在的元素 15
    int key;
    scanf("%d", &key);

    // 删除该元素
    if( search(root, key) != NULL ){
        //root=deleteNode(root, key); //方法1 递归删除
        //root=deleteNode_B(root, key); // 方法2 递归删除 优化：双子节点情况，只用一次遍历

        root=deleteNodeIterative(root, key); // 方法3 迭代删除

        printf("after deleting value: %d\n", key);

        // 3.打印树
        printTree(root, 0, "");
        inOrder(root);
        printf("\n");
    }else{
        printf("Value %d not in the tree\n", key);
    }

    // 释放内存
    freeTree(root);
}

int main(){
    demo1();
    return 0;
}